package offer

/*
时间复杂度：O(NlogC) C是元素数据范围 logC=log(2^32)==32
空间复杂度：O(1)

位运算

切片中每个数都出现N次，除了一个数只出现一次的问题可以用位运算
遍历32位的每一个bit位，则如果只出现一次的数该bit位为0，则所有数该bit位为1出现的次数一定是3的倍数;
否则将该bit位加到最终结果ans中
*/

func singleNumber(nums []int) int {
	ans := int32(0)
	for i := 0; i < 32; i++ {
		total := int32(0)
		for _, v := range nums {
			total += (int32(v) >> i) & 1
		}
		if total%3 != 0 {
			ans |= 1 << i
		}
	}
	return int(ans)
}
